package solution;


import java.util.Stack;

/*
* 84
* */
public class LargestRectangleArea {

    /*
    * 优化的暴力法
    * 使用两个数组记录每个数值的左右边界，然后计算最大值
    * */
    public int solution1(int[] heights) {
        if (heights == null || heights.length == 0){
            return 0;
        }

        int[] lessFromLeft = new int[heights.length];
        int[] lessFromRight = new int[heights.length];
        lessFromRight[heights.length - 1] = heights.length;
        lessFromLeft[0] = -1;

        for (int i = 1; i < heights.length; i++){
            int p = i - 1;

            while(p >= 0 && heights[p] >= heights[i]){
                p = lessFromLeft[p];
            }

            lessFromLeft[i] = p;
        }

        for (int i = heights.length - 2; i >= 0; i--){
            int p = i + 1;

            while(p < heights.length && heights[p] >= heights[i]){
                p = lessFromRight[p];
            }

            lessFromRight[i] = p;
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++){
            maxArea = Math.max(maxArea, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }

        return maxArea;
    }

    /*
    * 优化的使用栈
    * */
    public int solution2(int[] heights) {
        int len = heights.length;
        Stack<Integer> s = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= len ; i++){
            int h = (i == len ? 0 : heights[i]);

            if (s.isEmpty() || h >= heights[s.peek()]){
                s.push(i);
            }else {
                int tp = s.pop();
                maxArea = Math.max(maxArea, heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }

    /*
    * 单纯使用栈寻找左右边界
    * */
    public int sulution3(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0 ; i < n ; i++){
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0 ; i--){
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        int maxArea = 0;
        for (int i = 0 ; i < n ; i++){
            maxArea = Math.max(maxArea, (right[i] - left[i] - 1) * heights[i]);
        }
        return maxArea;
    }
}
